package org.zn.note.jdk.container;

import java.text.DecimalFormat;
import java.util.*;

/*
对 ArrayList 和 LinkedList 性能测试

关于遍历方式：用foreach就行
Type1：foreach
Type2：Iterator
Type3：for (int j = 0; j < list.size(); j++)
Type4: int size = list.size(); for (int j = 0; j < size; j++)  用变量先取出size
Type5：for (int j = list.size() - 1; j >= 0; j--)  倒着取

关于ArrayList和LinkedList对比：用ArrayList就行
1、在尾部插入数据，数据量较小时LinkedList比较快，因为ArrayList要频繁扩容，
   当数据量大时ArrayList比较快，因为ArrayList扩容是当前容量*1.5，大容量扩容一次就能提供很多空间，
   当ArrayList不需扩容时效率明显比LinkedList高，因为直接数组元素赋值不需new Node
2、在首部插入数据，LinkedList较快，因为LinkedList遍历插入位置花费时间很小，
   而ArrayList需要将原数组所有元素进行一次System.arraycopy
3、插入位置越往中间，LinkedList效率越低，因为它遍历获取插入位置是从两头往中间搜，
   index越往中间遍历越久，因此ArrayList的插入效率可能会比LinkedList高
4、插入位置越往后，ArrayList效率越高，因为数组需要复制后移的数据少了，那么System.arraycopy就快了，
   因此在首部插入数据LinkedList效率比ArrayList高，尾部插入数据ArrayList效率比LinkedList高
5、占用内存情况：管理80万数据，管理成本，LinkedList大概是ArrayList的6倍
6、LinkedList可以实现队列，栈等数据结构，这是它的优势

    比较ArrayList和LinkedList插入效率
    基础数据10万，分别在不同位置插入1万数据、删除1万数据
    开头  ArrayList 315ms  LinkedList 3ms    ArrayList 251ms  LinkedList 3ms
    1/4   ArrayList 195ms  LinkedList 950ms  ArrayList 190ms  LinkedList 723ms
    1/2   ArrayList 142ms  LinkedList 1869ms ArrayList 116ms  LinkedList 1647ms
    3/4   ArrayList 64ms   LinkedList 779ms  ArrayList 38ms   LinkedList 538ms
    结尾  ArrayList 6ms    LinkedList 107ms  ArrayList 1ms    LinkedList 1ms
（这里有一个问题，就是插入的时候，如果能直接有linkedlist位置指针的话，应该是linkedlist快）

    结论：
    1、同样实现（同时ArrayList或LinkedList），插入和删除差不多。
    2、只有在开头操作，LinkedList会快；其他情况都是ArrayList快。
    3、随即访问就更不用看了，ArrayList快。
 */
class ArrayListAndLinkedList {

    private static int FIRST_COLUMN_LENGTH = 23, OTHER_COLUMN_LENGTH = 12, TOTAL_COLUMN_LENGTH = 71;
    private static final DecimalFormat COMMA_FORMAT = new DecimalFormat("#,###");


    public static void printHeader(List<Integer>... listArray) {
        printRowDivider();
        for (int i = 0; i < listArray.length; i++) {
            if (i == 0) {
                StringBuilder sb = new StringBuilder().append("list size");
                while (sb.length() < FIRST_COLUMN_LENGTH) {
                    sb.append(" ");
                }
                System.out.print(sb);
            }

            StringBuilder sb = new StringBuilder().append("| ").append(COMMA_FORMAT.format(listArray[i].size()));
            while (sb.length() < OTHER_COLUMN_LENGTH) {
                sb.append(" ");
            }
            System.out.print(sb);
        }
        TOTAL_COLUMN_LENGTH = FIRST_COLUMN_LENGTH + OTHER_COLUMN_LENGTH * listArray.length;
        printRowDivider();
    }

    public static void printRowDivider() {
        System.out.println();
        StringBuilder sb = new StringBuilder();
        while (sb.length() < TOTAL_COLUMN_LENGTH) {
            sb.append("-");
        }
        System.out.println(sb);
    }

    public static void printCostTime(int i, int size, String caseName, long costTime) {
        if (i == 0) {
            StringBuilder sb = new StringBuilder().append(caseName);
            while (sb.length() < FIRST_COLUMN_LENGTH) {
                sb.append(" ");
            }
            System.out.print(sb);
        }

        StringBuilder sb = new StringBuilder().append("| ").append(costTime).append(" ms");
        while (sb.length() < OTHER_COLUMN_LENGTH) {
            sb.append(" ");
        }
        System.out.print(sb);

        if (i == size - 1) {
            printRowDivider();
        }
    }

    public static List<Integer>[] getArrayLists(int... sizeArray) {
        List<Integer>[] listArray = new ArrayList[sizeArray.length];
        for (int i = 0; i < listArray.length; i++) {
            long startTime = System.currentTimeMillis();
            int size = sizeArray[i];
            List<Integer> list = new ArrayList<Integer>();
            for (int j = 0; j < size; j++) {
                list.add(j);
            }
            long spend = System.currentTimeMillis() - startTime;
//            System.out.println("ArrayList insert " + size + " datas spends " + spend + " ms");
            listArray[i] = list;
        }
        return listArray;
    }

    public static List<Integer>[] getLinkedLists(int... sizeArray) {
        List<Integer>[] listArray = new LinkedList[sizeArray.length];
        for (int i = 0; i < listArray.length; i++) {
            long startTime = System.currentTimeMillis();
            int size = sizeArray[i];
            List<Integer> list = new LinkedList<Integer>();
            for (int j = 0; j < size; j++) {
                list.add(j);
            }
            long spend = System.currentTimeMillis() - startTime;
//            System.out.println("Linked insert " + size + " datas spends " + spend + " ms");
            listArray[i] = list;
        }
        return listArray;
    }

    public static void loopListCompare(List<Integer>... listArray) {
        printHeader(listArray);
        long startTime, endTime;

        // Type 2
        for (int i = 0; i < listArray.length; i++) {
            List<Integer> list = listArray[i];
            startTime = Calendar.getInstance().getTimeInMillis();
            // Iterator<Integer> iterator = list.iterator();
            // while(iterator.hasNext()) {
            // iterator.next();
            // }
            for (Iterator<Integer> iterator = list.iterator(); iterator.hasNext(); ) {
                iterator.next();
            }
            endTime = Calendar.getInstance().getTimeInMillis();
            printCostTime(i, listArray.length, "for iterator", endTime - startTime);
        }

        // Type 1
        for (int i = 0; i < listArray.length; i++) {
            List<Integer> list = listArray[i];
            startTime = Calendar.getInstance().getTimeInMillis();
            for (Integer j : list) {
                // use j
            }
            endTime = Calendar.getInstance().getTimeInMillis();
            printCostTime(i, listArray.length, "for each", endTime - startTime);
        }

        // Type 3
        for (int i = 0; i < listArray.length; i++) {
            List<Integer> list = listArray[i];
            startTime = Calendar.getInstance().getTimeInMillis();
            for (int j = 0; j < list.size(); j++) {
                list.get(j);
            }
            endTime = Calendar.getInstance().getTimeInMillis();
            printCostTime(i, listArray.length, "for list.size()", endTime - startTime);
        }

        // Type 4
        for (int i = 0; i < listArray.length; i++) {
            List<Integer> list = listArray[i];
            startTime = Calendar.getInstance().getTimeInMillis();
            int size = list.size();
            for (int j = 0; j < size; j++) {
                list.get(j);
            }
            endTime = Calendar.getInstance().getTimeInMillis();
            printCostTime(i, listArray.length, "for size = list.size()", endTime - startTime);
        }

        // Type 5
        for (int i = 0; i < listArray.length; i++) {
            List<Integer> list = listArray[i];
            startTime = Calendar.getInstance().getTimeInMillis();
            for (int j = list.size() - 1; j >= 0; j--) {
                list.get(j);
            }
            endTime = Calendar.getInstance().getTimeInMillis();
            printCostTime(i, listArray.length, "for j--", endTime - startTime);
        }
    }

    public static void randomAdd(List<Integer>... listArray) {
        long startTime = System.currentTimeMillis();
        Random random = new Random();
        for (List<Integer> list : listArray) {
            int size = list.size();
            for (int i = 0; i < 100; i++) {
                int index = random.nextInt(size - 1);
                list.add(index, i);
            }
        }
        long spend = System.currentTimeMillis() - startTime;
        System.out.println("randomAdd Spend " + spend + " ms");
    }

    /*
    指定位置插入或删除数据
     */
    private static final int INSERT = 1;
    private static final int DELETE = 2;
    private static void insertOrRemoveList(int option, List list, int offset, int counts) {
        int size = list.size();
        String type = "List";
        if (list instanceof ArrayList) {
            type = "ArrayList";
        } else if (list instanceof LinkedList) {
            type = "LinkedList";
        }
        // 在什么位置插入
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < counts; i++) {
            switch (option) {
                case INSERT: {
                    list.add(offset, counts);
                }
                case DELETE: {
                    if(offset == size) {
                        list.remove(offset-1-i);
                    } else {
                        list.remove(offset);
                    }
                }
            }
        }
        long spends = System.currentTimeMillis() - startTime;
        System.out.println(type + " 在[" + offset + "]位置处理[" + counts + "]数据 spends " + spends + " ms");
    }

    /*
    比较ArrayList和LinkedList插入效率
    基础数据10万，分别在不同位置插入1万数据、删除1万数据
    开头  ArrayList 315ms  LinkedList 3ms    ArrayList 251ms  LinkedList 3ms
    1/4   ArrayList 195ms  LinkedList 950ms  ArrayList 190ms  LinkedList 723ms
    1/2   ArrayList 142ms  LinkedList 1869ms ArrayList 116ms  LinkedList 1647ms
    3/4   ArrayList 64ms   LinkedList 779ms  ArrayList 38ms   LinkedList 538ms
    结尾  ArrayList 6ms    LinkedList 107ms  ArrayList 1ms    LinkedList 1ms
     */
    private static void insetList() {
        int baseDataNum = 100000;
        int[] baseDataNums = {baseDataNum, baseDataNum, baseDataNum, baseDataNum, baseDataNum};
        int insertDataNum = 10000;
        // 初始化10万数据
        List[] arrayLists = getArrayLists(baseDataNums);
        List[] linkedLists = getLinkedLists(baseDataNums);
        // 头部插入
        insertOrRemoveList(DELETE, arrayLists[0], 0, insertDataNum);
        insertOrRemoveList(DELETE, linkedLists[0], 0, insertDataNum);
        // 1/4 位置插入
        insertOrRemoveList(DELETE, arrayLists[1], baseDataNum/4*1, insertDataNum);
        insertOrRemoveList(DELETE, linkedLists[1], baseDataNum/4*1, insertDataNum);
        // 1/2 位置插入
        insertOrRemoveList(DELETE, arrayLists[2], baseDataNum/4*2, insertDataNum);
        insertOrRemoveList(DELETE, linkedLists[2], baseDataNum/4*2, insertDataNum);
        // 3/4 位置插入
        insertOrRemoveList(DELETE, arrayLists[3], baseDataNum/4*3, insertDataNum);
        insertOrRemoveList(DELETE, linkedLists[3], baseDataNum/4*3, insertDataNum);
        // 尾部插入
        insertOrRemoveList(DELETE, arrayLists[4], baseDataNum, insertDataNum);
        insertOrRemoveList(DELETE, linkedLists[4], baseDataNum, insertDataNum);
    }

    public static void main(String[] args) {
        insetList();


//        List[] list = getArrayLists(5000000, 5000000, 5000000, 5000000, 5000000);
//        List[] list2 = getLinkedLists(5000000, 5000000, 5000000, 5000000, 5000000);
//        randomAdd(list);
//        randomAdd(list2);
//        System.out.print("compare loop performance of ArrayList");
//        loopListCompare(list);
//
//        System.out.print("compare loop performance of ArrayList");
//        loopListCompare(list);

//        System.out.print("\r\n\r\ncompare loop performance of LinkedList");
//        loopListCompare(getLinkedLists(10000, 100000, 1000000, 9000000));
    }
}
